package baseclass.j_dp.dp.oneZeroBag;

import java.util.Arrays;

/**
 * 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 * <p>
 * 注意:
 * <p>
 * 每个数组中的元素不会超过 100
 * 数组的大小不会超过 200
 * 示例 1:
 * <p>
 * 输入: [1, 5, 11, 5]
 * <p>
 * 输出: true
 * <p>
 * 解释: 数组可以分割成 [1, 5, 5] 和 [11].
 * <p>
 * 分析题目本质：分成的两个子集和相等，就相当于求是否有某种组合能让 结果是 sum/2,回到数组目标和的问题。
 * <p>
 * 暴力回溯 + 记忆性回溯略。可见数组目标和问题
 *
 * @date 2020/3/2 21:21
 */
public class Code03_HalfSumArr {
    public boolean canPartition(int[] nums) {
        if(nums == null || nums.length <=1) return false;
        int sum = 0;
        for(int num : nums) sum += num;
        if((sum & 1) !=0 ) return false;
        sum = sum/2;
        return dp(nums,sum);
    }

    //方式3：正向DP，转01背包
    private boolean dp(int[] nums,int sum){
        boolean[] dp = new boolean[sum+1];

        for(int j = 0; j <= nums[0];j++){
            //决策第0号商品，能形成质量为0或nums[0]
            dp[j] = (j == 0 || j ==nums[0]);
        }
        for(int i=1; i< nums.length ; i++){
            for(int j = sum ; j >= nums[i]; j--){
                dp[j] = dp[j] || dp[j - nums[i]];
            }
        }
        return dp[sum];
    }

    //注意的是：直接暴力回溯肯定是超时的，但是可以优化，
    private static boolean process1(int[] nums){
        int sum = 0;
        for (int num : nums) sum += num;
        //如果sum是奇数，则不能平均为两个整数和
        if((sum & 1) != 0) return false;
        //对数组从大到小排序。由于数组类型不是Integer，所以无法使用比较器排序。
        //从大到小是为了加速过程。
        Arrays.sort(nums);
        reverse(nums);
        System.out.println(Arrays.toString(nums));
        return doProcess1(nums, 0,  0, sum/2);
    }

    /**
     * 方式1：暴力回溯，当前要或不要。优化后OJ可以通过测试，性能提升很大！
     * <p>
     * 统计是否能达到sum/2，当前位置可要可不要
     */
    private static boolean doProcess1(int[] nums, int index, int curSum, int sum) {
        if(index >= nums.length || curSum > sum || nums[index] > sum) return false;
        if(curSum == sum) {
            return true;
        }
        //当前位置要或当前位置不要
        return doProcess1(nums, index + 1, curSum + nums[index],  sum) ||
                doProcess1(nums, index + 1, curSum,  sum);
    }

    private static void reverse(int[] nums) {
        int left = 0;
        int right = nums.length -1;
        while (left < right){
            nums[left] = nums[left] ^ nums[right];
            nums[right] = nums[left] ^ nums[right];
            nums[left] = nums[left] ^ nums[right];
            left ++;
            right --;
        }
    }
}


